// 力扣87. 扰乱字符串

import java.util.*;

class Solution {
    // 记忆化缓存，存储已经计算过的结果
    private Map<String, Boolean> memo = new HashMap<>();

    public boolean isScramble(String s1, String s2) {
        // 基本情况：两个字符串相等，直接返回true
        if (s1.equals(s2)) {
            return true;
        }

        // 检查字符组成是否相同，如果不同直接返回false
        if (!hasSameChars(s1, s2)) {
            return false;
        }

        // 生成缓存键
        String key = s1 + "#" + s2;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int n = s1.length();

        // 尝试所有可能的分割点
        for (int i = 1; i < n; i++) {
            // 情况1：不交换分割后的两部分
            boolean noSwap = isScramble(s1.substring(0, i), s2.substring(0, i))
                    && isScramble(s1.substring(i), s2.substring(i));

            // 情况2：交换分割后的两部分
            boolean swap = isScramble(s1.substring(0, i), s2.substring(n - i))
                    && isScramble(s1.substring(i), s2.substring(0, n - i));

            if (noSwap || swap) {
                memo.put(key, true);
                return true;
            }
        }

        // 所有分割方式都不满足
        memo.put(key, false);
        return false;
    }

    // 辅助函数：检查两个字符串是否包含相同的字符（数量和种类都相同）
    private boolean hasSameChars(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }

        int[] count = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            count[s1.charAt(i) - 'a']++;
            count[s2.charAt(i) - 'a']--;
        }

        // 检查所有字符的计数是否为0
        for (int c : count) {
            if (c != 0) {
                return false;
            }
        }
        return true;
    }
}





// 力扣90. 子集 II
class Solution1 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        // 排序是去重的关键，让相同元素相邻
        Arrays.sort(nums);
        dfs(ans, new ArrayList<>(), nums, 0);
        return ans;
    }

    public void dfs(List<List<Integer>> ans, List<Integer> path, int[] nums, int start) {
        // 先添加当前路径（空路径也会被添加，对应初始状态）
        ans.add(new ArrayList<>(path));

        for(int i = start; i < nums.length; i++) {
            // 核心去重逻辑：跳过相同元素（确保相同元素只被选择一次）
            // i > start 保证不跳过第一个出现的元素，只跳过后续重复的
            if(i > start && nums[i] == nums[i-1]) {
                continue;
            }

            path.add(nums[i]);
            // 递归时从i+1开始，避免重复选择同一元素
            dfs(ans, path, nums, i + 1);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

